package com.msi.algorithm;

import java.util.ArrayList;
import java.util.List;

import org.apache.log4j.Logger;

import com.msi.Graph;
import com.msi.Main;
import com.msi.Vertex;

/**
 * Implementacja algorytmu CSP z nawrotami
 * @author Michał Kołodziejski
 */
public class CSPAlgorithm implements Runnable{
    
    /**
     * Rozpatrywany graf połączeń
     */
    protected Graph graph;
    
    /**
     * Drzewo stanów algorytmu przeszukiwania
     */
    protected StatesTree tree;
    
    /**
     * Aktualnie rozpatrywany stan częściowy
     */
    protected State currentState;
    
    /**
     * Flaga określająca, czy w poprzednim kroku algorytmu został dodany nowy stół
     */
    protected boolean newTableAtLastStep;

    /**
     * Logger
     */
    protected Logger logger = Logger.getLogger(CSPAlgorithm.class);
    
    protected boolean algorithmFinished;
    
    protected int minNumberOfTables;
    
    
    
    /**
     * Tworzy nową instancję implementacji algorytmu CSP z nawrotami
     * @param graph rozpatrywany graf
     */
    public CSPAlgorithm(Graph graph) {
        this.graph = graph;
        this.currentState = createInitialState();
        this.tree = new StatesTree(this.currentState);
        this.newTableAtLastStep = false;
        this.algorithmFinished = false;
        this.minNumberOfTables = (int) ((this.graph.getNumberOfVertices() + 3) / 4);
    }


    @Override
    public void run() {
        runAlgorithm();
    }

    
    /**
     * Uruchamia przetwarzanie algorytmu
     */
    public List<Table> runAlgorithm(){
        algorithmFinished = false;
        boolean finished = false;
        
        int step = 0;
        while(!finished){
            newTableAtLastStep = currentState.placeCurrentGuest();

            logger.debug("Step: " + step 
                    + ", sitting: " + currentState.getNumberOfSittingGuests()
                    + ", state: " + currentState.toString()
                    + ", min tables: " + minNumberOfTables);
            
            if(currentState.isStateFinal()){
                if(currentState.getTablesNumber() == minNumberOfTables){
                    // lepiej nie będzie - od razu zwracamy wynik
                    finished = true;
                    continue;
                }
                
                if(!newTableAtLastStep){
                    finished = true;
                    continue;
                }
            }
            
            currentState = chooseNextState();
            ++step;
        }
        
        algorithmFinished = true;
        
        return currentState.getTables();
    }
    
    
    /**
     * Zwraca informację, czy algorytm zakończył swoje działanie
     * @return informacja czy algorytm zakończył swoje działanie
     */
    public boolean isAlgorithmFinished(){
        // nie modyfikujemy tu wartości, więc dostęp nie musi być synchronizowany
        return this.algorithmFinished;
    }
    
    
    /**
     * Zwraca rezultat działania algorytmu
     * @return lista obsadzonych stołów
     */
    public List<Table> getResult(){
        if(!algorithmFinished){
            throw new RuntimeException("Próba pobrania wyniku przed zakończeniem działania algorytmu!");
        }
        
        return currentState.getTables();
    }
    
    
    /**
     * Tworzy stan początkowy dla drzewa
     * @return stan początkowy
     */
    protected State createInitialState(){
        Graph graphCopy = graph.getDeepCopy();
        List<Vertex> sortedVertices = graphCopy.getNotVisitedVerticesSortedByDegree(Main.ascendingSort); 
        Vertex firstVertex = sortedVertices.get(0);
        List<Table> tablesList = new ArrayList<Table>();
        
        State initialState = new State(graphCopy, firstVertex, tablesList, null);
        return initialState;
    }
    
    
    /**
     * Uaktualnia drzewo stanów
     */
    protected void updateStatesTree(){
        List<State> partialStates = tree.getPartialStatesCopy();
        
        for(State state : partialStates){
            if(!state.isStateFinal() && !state.mayHaveMoreChildrenStates()){
                tree.removePartialState(state);
            }
        }
    }
    
    
    /**
     * Wybiera kolejny stan
     * @return wybrany stan
     */
    protected State chooseNextState(){
        State bestState = currentState;
        
        // dopóki aktualny stan jest niegorszy niż najlepsze możliwe rozwiązanie - idziemy
        // dalej tą samą scieżką
        if(currentState.getTablesNumber() > minNumberOfTables){
        
            List<State> partialStates = tree.getPartialStatesCopy();
            
            // wybieramy stan o najmniejszej liczbie stołów, jeżeli jest to finalny
            bestState = partialStates.get(0);
            
            for(State state : partialStates){
                if(state.getTablesNumber() <= minNumberOfTables){
                    bestState = state;
                    break;
                }
                
                if(state.getTablesNumber() < bestState.getTablesNumber()){
                    bestState = state;
                    
                } else if(state.getTablesNumber() == bestState.getTablesNumber() 
                        && state.isStateFinal()){
                    bestState = state;
                    
                } else if(state.getTablesNumber() == bestState.getTablesNumber() 
                        && state.getNumberOfSittingGuests() > bestState.getNumberOfSittingGuests()){
                    bestState = state;
                }
            }
            
            if(bestState.isStateFinal()){
                // jeżeli końcowy - zwracamy od razu
                return bestState;
            }
            
        }
        
        // nie końcowy - tworzymy stan potomny i ew. usuwamy aktualny
        State nextState = bestState.createNewChildState();
        if(nextState.mayHaveMoreChildrenStates()){
            tree.addPartialState(nextState);
        }
        updateStatesTree();
        
        return nextState;
    }
}
